/*
day264
2020.5.18
*/
#include<vector>
#include<iostream> 
using namespace std;
 

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    void recoverTree(TreeNode* root) {
        vector<int> vec;
        inorder(vec,root);
        vector<int> res = findSwap(vec);
        change(root,res);
    }
    
    void change(TreeNode *root,const vector<int> &vec)
    {
    	if(!root)
    	{
    		return ;
		}
    	change(root->left,vec);
    	
    	if(root->val==vec[0] || root->val==vec[1])
    	{
    		root->val = root->val==vec[0] ? vec[1] : vec[0]; 
		}
    	
    	change(root->right,vec);
	}
    
    vector<int> findSwap(const vector<int> &vec)
    {
    	vector<int> res;
    	int count=0;
    	int next=0;
    	for(int i=0;i<vec.size()-1;++i)
    	{
    		if(vec[i]>vec[i+1])
    		{
    			if(count==0)
    			{
    				res.push_back(vec[i]);
    				next=vec[i+1];
    				count++;
				}
				else
				{
					res.push_back(vec[i+1]);
					count++;
				}
			}
		}
		if(count==1)
		{
			res.push_back(next);
		}
		return res;
	}
	
	void inorder(vector<int> &vec,TreeNode *root)
	{
		if(!root)
		{
			return ;
		}
		
		inorder(vec,root->left);
		
		vec.push_back(root->val);
		
		inorder(vec,root->right);
	}
};

int main()
{
	Solution s;
	vector<int> vec={3,2,1};
	vector<int> res=s.findSwap(vec); 
	for(int i=0;i<res.size();i++)
	{
		cout<<res[i]<<'\t'; 
	} 
	return 0;
}
    	
    	
        
   
